package com.c2b.algorithm.leetcode.hot100;

/**
 * <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/">在排序数组中查找元素的第一个和最后一个位置</a>
 * <p>
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 * </p>
 * <pre>
 * 示例 1：
 *      输入：nums = [5,7,7,8,8,10], target = 8
 *      输出：[3,4]
 *
 * 示例 2：
 *      输入：nums = [5,7,7,8,8,10], target = 6
 *      输出：[-1,-1]
 *
 * 示例 3：
 *      输入：nums = [], target = 0
 *      输出：[-1,-1]
 * </pre>
 * <b>提示：</b>
 * <li>0 <= nums.length <= 10^5</li>
 * <li>-10^9 <= nums[i] <= 10^9</li>
 * <li>nums 是一个非递减数组</li>
 * <li>-10^9 <= target <= 10^9</li>
 *
 * @author c2b
 * @since 2022/5/5 9:25
 */
public class Hot0034SearchRange_M {

    /**
     * 二分查找
     *
     * @param nums   按照升序排列的整数数组
     * @param target 目标值
     * @return 给定目标值在数组中的开始位置和结束位置
     * @author c2b
     * @since 2022/5/5 9:26
     */
    public int[] searchRange(int[] nums, int target) {
        int length;
        int[] res = {-1, -1};
        if (nums == null || (length = nums.length) < 1) {
            return res;
        }
        int leftIndex = 0;
        int rightIndex = length - 1;
        int midIndex;
        while (leftIndex <= rightIndex) {
            midIndex = leftIndex + ((rightIndex - leftIndex) >> 1);
            if (nums[midIndex] < target) {
                leftIndex = midIndex + 1;
            } else if (nums[midIndex] > target) {
                rightIndex = midIndex - 1;
            } else {
                // 通过二分查找找到一个符合题意的位置
                // 向左扩大范围
                for (int i = midIndex; i >= leftIndex && nums[i] == target; --i) {
                    res[0] = i;
                }
                // 向右扩大范围
                for (int j = midIndex; j <= rightIndex && nums[j] == target; ++j) {
                    res[1] = j;
                }
                return res;
            }
        }
        return res;
    }

    /**
     * 递归实现二分查找
     *
     * @param nums   按照升序排列的整数数组
     * @param target 目标值
     * @param lower
     * @return 给定目标值在指定数组范围上的位置
     * @author c2b
     * @since 2022/5/5 9:30
     */
    private static int binarySearch(int[] nums, int target, boolean lower) {
        return 0;
    }

    public static void main(String[] args) {
        Hot0034SearchRange_M hot0034SearchRange = new Hot0034SearchRange_M();
        for (int i : hot0034SearchRange.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)) {
            System.out.println(i);
        }
    }

}
